class Solution {
public:
    /**
     * find median in two sorted array
     * @param arr1 int整型vector the array1
     * @param arr2 int整型vector the array2
     * @return int整型
     */
    int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
        // write code here
        //s1，d1指向第一个数组的边界,m1指向数组的中间位置
        /*
        将两个数组的mid值进行比较
        如果arr1[mid]=arr2[mid],mid所指即为所求
        如果arr1[mid]<arr2[mid];删除arr1中较小的一半，删除arr2中较大的一半，要求两次删除元素个数相等
        如果arr1[mid]>arr2[mid];删除arr1中较大的一半，同时删除arr2中较小的一半，要求两次删除元素个数相等
        到最后两个数组中只含有一个元素，返回较小的那个
        */  
        int s1=0,d1=arr1.size()-1,m1;
        int s2=0,d2=arr2.size()-1,m2;
        while(s1!=d1||s2!=d2)
        {
            m1=(s1+d1)/2;
            m2=(s2+d2)/2;
            if(arr1[m1]==arr2[m2])
                return arr1[m1];
            if(arr1[m1]<arr2[m2])
            {
                if((s1+d1)%2==0)//奇数个
                {
                    s1=m1;
                    d2=m2;
                }
                else//如果数组个数是偶数个，则删除arr1中较小的一半，包含mid;删除arr2中较大的一半，不包含mid
                {
                    s1=m1+1;
                    d2=m2;
                }
            }
            else
            {
                if((s2+d2)%2==0)
                {
                    s2=m2;
                    d1=m1;
                }else{
                    d1=m1;
                    s2=m2+1;
                }
            }
        }
         return arr1[s1]<arr2[s2]?arr1[s1]:arr2[s2];
    }
   
};